#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 1e4 + 10;
const int MAXM = 1e5 + 10;
const int MAXI = 0x7fffffff;

struct EDGE {
    int src;
    int dest;
    int dis;
    EDGE() { src = 0, dest = 0, dis = 0; }
    EDGE(int f, int t, int d) { src = f, dest = t, dis = d; }
};

struct QUE_NODE {
    int id;
    int val;
    bool operator<(const QUE_NODE n) const { return val < n.val; }
    bool operator>(const QUE_NODE n) const { return val > n.val; }
    bool operator==(const QUE_NODE n) const { return val == n.val; }
    bool operator<=(const QUE_NODE n) const { return val < n.val || val == n.val; }
    bool operator>=(const QUE_NODE n) const { return val > n.val || val == n.val; }
    bool operator!=(const QUE_NODE n) const { return !(val == n.val); }

    QUE_NODE(int i, int v) { id = i, val = v; }
};

int N, M;
vector<int> val(MAXN);
vector<int> min_dis(MAXN, MAXI);
vector<bool> vis(MAXN, 0);
vector<vector<EDGE>> edges(MAXN, vector<EDGE>(0));

typedef priority_queue<QUE_NODE, vector<QUE_NODE>, greater<QUE_NODE>> PQ;
// priority_queue<

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> val[i];
    for (int i = 1; i <= M; i++) {
        int src, dest, dis;
        cin >> src >> dest >> dis;
        edges[src].push_back(EDGE(src, dest, dis));
        edges[dest].push_back(EDGE(dest, src, dis));
    }

    PQ que;
    que.push(QUE_NODE(1, 0));
    min_dis[1] = 0;

    while (!que.empty()) {
        // printPriorityQueue(que);
        auto src_node = que.top();
        int id = src_node.id;
        int pre = src_node.val;
        que.pop();

        if (vis[id])
            continue;
        else
            vis[id] = true;

        for (auto it = edges[id].begin(); it != edges[id].end(); it++) {
            int des = it->dest;
            int dis = it->dis;

            if (min_dis[des] < pre + dis + val[des]) continue;
            min_dis[des] = pre + dis + val[des];
            if (!vis[des]) que.push(QUE_NODE(des, pre + dis + val[des]));
        }
    }

    cout << min_dis[N] - val[N];
    // for (int i = 1; i <= N; i++) cout << i << ": " << min_dis[i] << endl;
}